⟸ Go Back ⟸

Exercise 5 (Homework 6).

(R (decidable/recursive languages), RE (semi-decidable/ recursively enumerable languages), coRE)

Classification V: properties of computable functions

For each of the following languages L, decide whether L\in \mathbf{R}, L\in \mathbf{RE}\setminus \mathbf{R}, L\in \mathbf{coRE}\setminus \mathbf{R}, or L\notin \mathbf{RE}\cup \mathbf{coRE}.

1. \{p \mid \varphi_p \text{ is injective}\}
2. \{p \mid \varphi_p \text{ is total and injective}\} (solving this RACSO exercise might give some hints)
3. \{p \mid \varphi_p \text{ is onto}\}
4. \{p \mid \varphi_p \text{ is total and onto}\}
5. \{p \mid \varphi_p \text{ is increasing}\}
6. \{p \mid \varphi_p \text{ is total and increasing}\}
7. \{p \mid \varphi_p \text{ is strictly decreasing}\}
8. \{p \mid \varphi_p \text{ is total and strictly decreasing}\}
9. \{p \mid \forall y > p\ \varphi_y \text{ is bijective}\}
10. \{p \mid \forall y < p\ \varphi_y \text{ is bijective}\}
11. \{p \mid \exists y > p\ \varphi_y \text{ is bijective}\}
12. \{p \mid \exists y < p\ \varphi_y \text{ is bijective}\}